package com.ting.test.algorithms.strings;

import java.util.Arrays;

/**
 * Created by 雷霆 on 2021/1/22.
 * <p>
 * Description：
 * N皇后问题是指在N*N的棋盘上要摆N个皇后，
 * 要求任何两个皇后不同行、不同列， 也不在同一条斜线上
 * 给定一个整数n，返回n皇后的摆法有多少种。  n=1，返回1
 * n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0
 * n=8，返回92
 */
public class NQueen {
    public static void main(String[] args) {
        int n = 5;
        //此处用一个一维数组代替一个二维数组,表示一个坐标点
        // record的第n个元素的index表示行 第n个元素的value表示列 即(n,record[n])
        int[] record = new int[n];
        //表示当第i-1行之前的皇后的位置已经确定的情况下，第I行之后（包括第I行）共有多少种情况
        int total = process(record, 0);
        System.out.println(total);
    }

    private static int process(int[] record, int i) {
        //base case 如果index已经走到头 则表示n个皇后都已经找到了自己的位置 且这种情况是有效的
        if (i == record.length) {
            return 1;
        }

        int result = 0;
        // 下面的遍历 表示 在第i行 遍历每一个可以放置皇后的位置，并且计算当把皇后放在该位置后，
        // 后面的(i+1之后)其他皇后一共有多少种摆法
        for (int j = 0; j < record.length; j++) {
            // 如果在第i行,第j列能够放置皇后，则看下第
            if (isValid(record, i, j)) {
                record[i] = j;//将第i行，j列置为已使用 即坐标(i,record[i])被使用
                result += process(record, i + 1);
            }
        }

        return result;
    }

    private static boolean isValid(int[] record, int i, int j) {
        for (int k = 0; k < i; k++) {
            //根据要求如果两个皇后同列是不行的 因此record[k]==j 表示在第j列上 有跟之前的皇后同列了 不符合要求
            //任意两个皇后如果同对角线也是不行的，
            // 即新坐标(i,j)和之前已经摆好的皇后坐标(k,record[k])不能同对角线
            //可以发现(|i-k|==|record[k]-j|)的时候 两个坐标同对角线
            //因此 得到以下公式
            if (record[k] == j || Math.abs(record[k] - j) == Math.abs(k - i)) {
                return false;
            }

        }
        return true;
    }
}
